# 对链表进行插入排序： https://leetcode-cn.com/problems/insertion-sort-list/submissions/

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode: 
        """
            就是插入排序， 
            1. 元素个数小于2时，直接返回
            2. 定义 i j 指针， i 及 i 前面的位是排好序的， j为 未排序的第一个元素
            3. 不能使用从 i 往前找的方式， 因为 i 指针不能够前移， 所以每次都是从前往后找
        """
        # 元素下雨等于1， 直接返回了
        if not head or not head.next:
            return head

        # 加入 首元结点， 统一加入节点的逻辑
        dumpy = ListNode(0, head)
        i = head
        j = head.next
        while j:
            p = dumpy
            if i.val > j.val:
                # 顺序查找插入位置，从前往后
                while p.next and p.next.val < j.val:
                    p = p.next 
                
                # 插入
                i.next = j.next
                temp = j
                j = j.next
                temp.next = p.next
                p.next = temp

            else:
                i = i.next
                j = j.next
        
        return dumpy.next

"""
对于上面的 插入操作，我是使用一个变量代替当前的节点， j 就后移了
这样写可能 逻辑更清晰

i.next = j.next
j.next = p.next
p.next = j

# 最后再将 j移动到 i 后面一位
j = i.next
"""
